package path;

import java.util.ArrayList;

public class Graph {

    static class Node {

        ArrayList<Integer> nodes = new ArrayList<Integer>();
        ArrayList<Boolean> nodpas = new ArrayList<Boolean>();

        public Node() {
        }

        public void add(int n) {
            nodes.add(n);
            nodpas.add(Boolean.FALSE);
        }
    };
    private ArrayList<Node> lGraph = new ArrayList<Node>();

    public Graph() {
    }

    public void add() {
        lGraph.add(new Node());
    }

    public void addArc(int n, int m) {
        lGraph.get(n).add(m);
        lGraph.get(m).add(n);
    }

    public int getPathLength(int first, int second) {
        boolean b = true;
        int max = 0;
        for (int i = 0; i < lGraph.get(first).nodpas.size(); i++) {
            b = b && lGraph.get(first).nodpas.get(i);
            if (!lGraph.get(first).nodpas.get(i)) {
                lGraph.get(first).nodpas.set(i, Boolean.TRUE);
                lGraph.get(lGraph.get(first).nodes.get(i)).nodpas.set(lGraph.get(lGraph.get(first).nodes.get(i)).nodes.indexOf(first), Boolean.TRUE);
                int n = getPathLength(lGraph.get(first).nodes.get(i), second);
                if (n > max) {
                    max = n;
                }
                lGraph.get(first).nodpas.set(i, Boolean.FALSE);
                lGraph.get(lGraph.get(first).nodes.get(i)).nodpas.set(lGraph.get(lGraph.get(first).nodes.get(i)).nodes.indexOf(first), Boolean.FALSE);
            }
        }
        if (b && first != second) {
            return -1;
        } else {
            return max + 1;
        }
    }

    public int[] getLongestPath() {
        int[] z = new int[3];
        int max,f,s;
        max=f=s=0;
        for(int i=0;i<lGraph.size();i++){
            for(int j=0;j<lGraph.size();j++){
                int n=getPathLength(i,j);
                if(n>max){
                    max=n;
                    f=i;
                    s=j;
                }
            }
        }
        z[0]=max;
        z[1]=f;
        z[2]=s;
        return z;
    }
}